#ifdef __STDC_VERSION__
#if __STDC_VERSION__ < 199901L
#error Rok 1999 już dawno za nami. Czas uaktualnić kompilator!
#endif
#else
#error Rok 1999 już dawno za nami. Czas uaktualnić kompilator!
#endif

#include"przeksztalcenia2.h"

/* Małe liczby pierwsze do trywialnego sprawdzenia pierwszości */
unsigned long int pierwsze[]={
      2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,
     53,  59,  61,  67,  71,  73,  79,  83,  89,  97, 101, 103, 107, 109, 113,
    127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
    199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
    283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
    383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
    467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571,
    577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
    661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761,
    769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
    877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977,
    983, 991, 997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
   1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,
   1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,
   1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,
   1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,
   1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,
   1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,
   1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,
   1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,
   1993,1997,1999,
};

/* Stan generatora liczb losowych */
static gmp_randstate_t stan;
/* 
 * Elementy algorytmu generowania liczb losowych generatora Bluma-Micalego,
 * zgodnie z opisem w "Bruce Schneier, Applied Cryptography...".
 * p12=(p-1)/2
 */
static mpz_t x,g,p,p12;

/* inicjalizacja biblioteki wielkich liczb */
void inicjalizuj(void)
{
   gmp_randinit_default(stan);
   mpz_init(x);
   mpz_init(g);
   mpz_init(p);
}

/* 
 * Sprawdzenie czy liczba nie jest pierwsza w sposób trywialny
 * (podzielna przez pewną małą liczbę pierwszą).
 */
bool czyTrywialniePierwsza(const mpz_t liczba)
{
   unsigned int i;

   for(i=0; i<sizeof(pierwsze)/sizeof(unsigned long int); ++i)
   {
      if(mpz_divisible_ui_p(liczba,pierwsze[i])!=0)
      {
	 return false;
      }
   }
   return true;
}

/* Test Millera-Rabina na to czy liczba jest liczbą pseudopierwszą */
bool czyMilleraRabinaPierwsza(const mpz_t p)
{
   signed char i;
   unsigned char j;
   /*
    * Poniższe zmienne to elementy algorytmu Millera-Rabina.
    * Implementacja wg. "Bruce Schneier, Applied Cryptography..."
    */
   unsigned long int b;
   mpz_t p1,m,a,z;
   mpz_init(p1); //p1=p-1, przydatna w kilku krokach algorytmu
   mpz_init(m);
   mpz_init(a);
   mpz_init(z);
   mpz_sub_ui(p1,p,1);
   b=mpz_scan1(p1,1);
   mpz_tdiv_q_2exp(m,p1,b);
   for(i=0; i<testMilleraRabinaPowtorzenia; ++i)
   {
      mpz_urandomm(a,stan,p); //losowanie liczby
      if(mpz_cmp_ui(a,2)<=0) //czy parzysta? jeśli tak, to kontynuuj
      {
	 --i;
	 continue;
      }
      /* Początek algorytmu Millera-Rabina */
      mpz_powm(z,a,m,p);
      if(mpz_cmp_ui(z,1)==0 || mpz_cmp(z,p1)==0) //czy z=1 lub z=p-1?
	 continue;
      for(j=1;j<b;++j)
      {
	 mpz_powm_ui(z,z,2,p);
	 if(mpz_cmp_ui(z,1)==0) //czy z=1?
	    return false;
	 if(mpz_cmp(z,p1)==0) //czy z=p-1
	    break;
      }
      if(j==b) //jeżeli przeszedł cały algorytm to liczba nie pseudopierwsza
      {
	 return false;
      }
   }
   return true;
}

/* 
 * Losowe generowanie liczb i sprawdzanie czy nie są pierwsze.
 * Zwracana jest pierwsza odnaleziona liczba pseudopierwsza.
 */
void generujPierwsza(mpz_t liczba)
{
   do
   {
      mpz_urandomb(liczba,stan,bityPierwszej);
      mpz_setbit(liczba,0); //ostatni bit na 1, aby liczba była nieparzysta
      mpz_setbit(liczba,bityPierwszej-1);//pierwszy bit na 1 aby wystarczająco długa
   }
   while(!czyTrywialniePierwsza(liczba) || !czyMilleraRabinaPierwsza(liczba));
}

/* Ustawienie wartości początkowej generatora Bluma-Micalego */
void ustawZiarno(mpz_t z)
{
   mpz_set(x,z);
}

/* Ustawienie liczby g z opisu algorytmu */
void ustawG(mpz_t gg)
{
   mpz_set(g,gg);
}

/* Ustawienie liczby p z opisu algorytmu */
void ustawP(mpz_t pp)
{
   mpz_set(p,pp);
   mpz_sub_ui(p12,p,1);
   mpz_tdiv_q_2exp(p12,p12,1);
}

/* Generuje kolejną liczbę przy użyciu algorytmu Bluma-Micalego */
unsigned char nastepny(void)
{
   unsigned char i,wyjscie=0;
   for(i=0;i<8;++i)
   {
      wyjscie <<=1;
      mpz_powm(x,g,x,p);
      if(mpz_cmp(x,p12)<0)
      {
	 wyjscie |= 1;
      }
   }
   return wyjscie;
}

/* 
 * Funkcja szyfrująca i deszyfrująca.
 * W tym algorytmie są to te same funkcje
 */
unsigned char szydefruj(unsigned char wejscie)
{
   return wejscie ^ nastepny();
}

unsigned char szydefruj2(unsigned char wejscie, mpz_t klucz)
{
   unsigned char i,wyjscie=0;
   for(i=0;i<8;++i)
   {
      wyjscie <<=1;
      mpz_powm(klucz,g,klucz,p);
      if(mpz_cmp(klucz,p12)<0)
      {
	 wyjscie |= 1;
      }
   }
   return wejscie ^ wyjscie;
}
